#include <iostream>
#include <vector>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <memory>

// 顶点类，表示图中的节点
class Vertex {
private:
    std::string name;                  // 顶点名称（如"A", "B"等）
    std::vector<Vertex*> neighbors;    // 相邻顶点（指向的顶点）
    std::vector<Vertex*> predecessors; // 前置顶点（指向当前顶点的顶点）
    size_t nbytes;                     // 容量大小
    size_t accumulatedBytes;           // 累加后的字节数

public:
    // 构造函数，默认nbytes为1024
    Vertex(const std::string& n, size_t nb = 1024) 
        : name(n), nbytes(nb), accumulatedBytes(0) {}

    // 获取顶点名称
    std::string getName() const {
        return name;
    }

    // 获取nbytes值
    size_t getNBytes() const {
        return nbytes;
    }

    // 设置nbytes值
    void setNBytes(size_t nb) {
        nbytes = nb;
    }

    // 获取累加后的字节数
    size_t getAccumulatedBytes() const {
        return accumulatedBytes;
    }

    // 设置累加后的字节数
    void setAccumulatedBytes(size_t ab) {
        accumulatedBytes = ab;
    }

    // 添加相邻顶点（边）
    void addNeighbor(Vertex* neighbor) {
        neighbors.push_back(neighbor);
    }

    // 添加前置顶点
    void addPredecessor(Vertex* predecessor) {
        predecessors.push_back(predecessor);
    }

    // 获取所有相邻顶点
    const std::vector<Vertex*>& getNeighbors() const {
        return neighbors;
    }

    // 获取所有前置顶点
    const std::vector<Vertex*>& getPredecessors() const {
        return predecessors;
    }

    // 打印顶点信息，无后续边时不显示箭头
    void printInfo() const {
        std::cout << name << " [nbytes: " << nbytes 
                  << ", accumulated: " << accumulatedBytes << "]";
        
        // 只有当有邻居时才显示箭头和邻居列表
        if (!neighbors.empty()) {
            std::cout << " -> ";
            for (size_t i = 0; i < neighbors.size(); ++i) {
                if (i > 0) {
                    std::cout << ", ";
                }
                std::cout << neighbors[i]->getName();
            }
        }
        std::cout << std::endl;
    }
};

// 图类，管理所有顶点和边
class Graph {
private:
    std::unordered_map<std::string, std::unique_ptr<Vertex>> vertices;  // 存储所有顶点
    std::vector<Vertex*> topologicalOrder;  // 存储顶点的拓扑排序

public:
    // 添加顶点
    Vertex* addVertex(const std::string& name, size_t nbytes = 1024) {
        // 如果顶点不存在，则创建
        if (vertices.find(name) == vertices.end()) {
            vertices[name] = std::make_unique<Vertex>(name, nbytes);
        }
        return vertices[name].get();
    }

    // 添加边（从from顶点到to顶点）
    void addEdge(const std::string& from, const std::string& to) {
        Vertex* fromVertex = addVertex(from);  // 确保起点存在
        Vertex* toVertex = addVertex(to);      // 确保终点存在
        fromVertex->addNeighbor(toVertex);     // 添加边（邻居关系）
        toVertex->addPredecessor(fromVertex);  // 添加前置关系
    }

    // 获取顶点
    Vertex* getVertex(const std::string& name) {
        auto it = vertices.find(name);
        if (it != vertices.end()) {
            return it->second.get();
        }
        return nullptr;
    }

    // 执行拓扑排序并存储结果
    void computeTopologicalOrder() {
        topologicalOrder.clear();
        
        // 计算每个顶点的入度
        std::unordered_map<Vertex*, int> inDegree;
        for (const auto& pair : vertices) {
            Vertex* v = pair.second.get();
            inDegree[v] = v->getPredecessors().size();
        }

        // 初始化队列，入度为0的顶点入队
        std::queue<Vertex*> q;
        for (const auto& pair : inDegree) {
            if (pair.second == 0) {
                q.push(pair.first);
            }
        }

        // 执行拓扑排序
        while (!q.empty()) {
            Vertex* current = q.front();
            q.pop();
            topologicalOrder.push_back(current);

            // 减少邻居的入度
            for (Vertex* neighbor : current->getNeighbors()) {
                inDegree[neighbor]--;
                if (inDegree[neighbor] == 0) {
                    q.push(neighbor);
                }
            }
        }
    }

    // 计算所有顶点的累加字节数（按数据流向：自身+所有前置节点的累加值）
    void calculateAllAccumulatedBytes() {
        // 首先计算拓扑顺序
        computeTopologicalOrder();

        // 按拓扑顺序计算累加值
        for (Vertex* v : topologicalOrder) {
            // 初始值为自身nbytes
            size_t total = v->getNBytes();
            
            // 加上所有前置节点的累加值
            for (Vertex* pred : v->getPredecessors()) {
                total += pred->getAccumulatedBytes();
            }
            
            v->setAccumulatedBytes(total);
        }
    }

    // 按拓扑排序顺序打印整个图的结构
    void print() const {
        std::cout << "图结构如下（按数据流向顺序）：" << std::endl;
        for (Vertex* v : topologicalOrder) {
            v->printInfo();
        }
    }
};

int main() {
    // 创建图
    Graph graph;

    // 添加边，同时会自动创建顶点（默认nbytes为1024）
    graph.addEdge("A", "B");   // A将输出给B
    graph.addEdge("B", "C");   // B将输出给C
    graph.addEdge("B", "F");   // B将输出给F
    graph.addEdge("C", "D");   // C将输出给D
    graph.addEdge("D", "F");   // D将输出给F
    graph.addEdge("F", "G");   // F将输出给G

    // 计算所有顶点的累加字节数（按正确顺序）
    graph.calculateAllAccumulatedBytes();

    // 按拓扑排序顺序打印图结构及累加结果
    graph.print();

    return 0;
}
